题目链接
题解
满满的反演的套路的味道
常规操作枚举约数
上面的式子可以化为
对于右上角的式子
很眼熟…推下式子
令$p=id$那么原式变成了
对于每个$p$,令$F[p]=\prod_{d|p} f[d]^{\mu(\frac{p}{d})}$,$F[p]$的值是固定的,用筛法求出$F[p]$,做前缀积,对与$\left \lfloor \frac{n}{p} \right \rfloor \left \lfloor \frac{m}{p} \right \rfloor$数论分块一下
复杂度为$O((n+T\sqrt{n})log(1e9+7))$
代码
|
|